package stack.test85;

import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/22 12:47
 */
public class Solution1 {

    // 单调栈的解法
    public int maximalRectangle(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] temp = new int[n];
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                temp[j] = matrix[i][j] == '0' ? 0 : temp[j] + 1;
            }
            // 计算当前数组组成的最大矩阵面积
            ans = Math.max(ans, helper(temp));
        }
        return ans;
    }

    private int helper(int[] arr){
        int ans = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        int curH, left, right;
        for(int i = 0; i < arr.length; ){
            if(stack.isEmpty() || arr[i] > arr[stack.peek()]){
                stack.push(i++);
            }else{
                curH = arr[stack.pop()];
                left = stack.isEmpty() ? -1 : stack.peek();
                right = i;
                ans = Math.max(ans, (right - left - 1) * curH);
            }
        }
        while(!stack.isEmpty()){
            curH = arr[stack.pop()];
            left = stack.isEmpty() ? -1 : stack.peek();
            right = arr.length;
            ans = Math.max(ans, (right - left - 1) * curH);
        }
        return ans;
    }
}
